package com.taobao.ad.hadoop.common;
import java.util.*;

public class Heap {
	public Heap(){
		data = new ArrayList<Pair>();
		this.heapSize = Integer.MAX_VALUE;
	}
	public int getHeapSize() {
		return heapSize;
	} 
	public void setHeapSize(int heapSize) {
		this.heapSize = heapSize;
	}
	public List<Pair> getData(){
		return data;
	}
	public void sort(){
		int size = data.size();
		for(int i = size - 1; i >= 0; i --){
			Pair x = data.get(0);
			data.set(0, data.get(i));
			data.set(i, x);
			sink(0, i);
		}
	}
	public void push(Pair pair){
		if(data.size() == 0){
			data.add(pair);
		}else{
			if(data.size() < heapSize){
				data.add(pair);
				raise(data.size() -1);
			}else{
				if(data.get(0).compareTo(pair) < 0){
					data.set(0, pair);
					sink(0,data.size());
				}
			}
		}
	}
	private void sink(int start, int end){
		int i, j;
		Pair pair = data.get(start);
		for(i = start,  j = 2 * i + 1; j < end; i = j, j = 2 * i + 1){
			if(j < end -1 && data.get(j).compareTo(data.get(j + 1)) > 0){
				j ++;
			}
			if(pair.compareTo(data.get(j)) < 0){
				break;
			}else{
				data.set(i, data.get(j));
			}
		}
		data.set(i, pair);
	}
	private void raise(int start){
		int i, j;
		Pair pair = data.get(start);
		for(j = start, i = (j - 1) / 2; j > 0; j = i, i = (j - 1) / 2){
			if(pair.compareTo(data.get(i)) > 0){
				break;
			}else{
				data.set(j, data.get(i));
			}
		}
		data.set(j, pair);
	}  
	private int heapSize;
	private List<Pair> data;
}

